Traditional digital computers use arrays of transistors to perform operations over binary data—that is, series of bits which have two possible values: “on” and “off”, “high” and “low”, 0 and 1, etc. Massive advancements in this technology have been made over the past century, to the point where a computer that fits in one's pocket can outperform computers that previously spanned multiple rooms. This is due in large part to the shrinking of the transistor and the continuously compressing more transistors onto smaller chips. However, certain physical laws restrict this process from repeating indefinitely and as such the speed of digital computers will eventually reach a plateau. Hence researchers have been looking to other types of computation as ways of progressing beyond this bound.
Quantum computers, first devised in 1982 by Richard Feynman, use the principles of quantum mechanics to perform computations. These computational devices can exploit, for example, phenomena such as “quantum parallelism” whereby computations are, in effect, performed on an exponential number of input states simultaneously. In fact, algorithms have been devised exploiting such effects to theoretically out-perform best known classical algorithms—for example, Shor's algorithm provides an exponential speed-up over the best known classical algorithm for factoring numbers.
These theoretical benefits are subject to certain “crossover points,” the instance size after which a quantum algorithm begins to outperform a classical one. The crossover points are influenced by a variety of factors, including the cost of the implementation of the algorithm in the form of a quantum circuit. To reduce the crossover points, at which point the overhead of performing quantum computation is less than the theoretical speedup, it is therefore an object of research to develop methods by which the cost of quantum circuits may be reduced, a process which is referred to as circuit optimization.